package com.maomao.algorithm;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

/**
 *
 * @author xiaomin
 * @date 2018/5/11
 */
public class FindK {
    public static int partition(int[] a, int low, int high) {
        int key = a[low];
        while (low < high) {
            while (low < high && a[high] >= key) {
                high--;
            }
            a[low] = a[high];
            while (low < high && a[low] <= key) {
                low++;
            }
            a[high] = a[low];
        }
        a[low] = key;
        return low;
    }

    public static int quickSelect(int[] a, int low, int high, int k) {

        if (low == high) {
            return a[low];
        }
        int keyPos = partition(a, low, high);

        int num = keyPos - low + 1;
        if (num == k) {
            return a[keyPos];
        } else if (k < num) {
            return quickSelect(a, low, keyPos - 1, k);
        } else {
            return quickSelect(a, keyPos + 1, high, k - num);
        }

    }

    private List<Integer> list;
    /**
     * 先取出前K个数排序，再从后面依次插入
     * @param k
     * @return
     *
     * Date	  :2012-7-4
     * Author :GongQiang
     */
    public int kSortThenCompare( int k ){
        List<Integer> result = new ArrayList<Integer>( k );
        for( int i=0 ; i<k ; i++ ){
            result.add( list.get(i) );
        }

        //前K位数，按照从大到小排序
        Collections.sort( result, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                if( o1 > o2 ){
                    return -1;
                }
                if( o1< o2 ){
                    return 1;
                }
                return 0;
            }
        });

        // 后 K+1 位数与前面的有序数组比较，插入适当的位置
        for( int i=k ; i<list.size() ; i++ ){
            int j = k-1;
            while( j>=0 && list.get(i) > result.get(j) ){
                j--;
            }

            if( 0<=j && j<k-1 && list.get(i) < result.get(j) ){
                result.add( j+1, list.get(i) );
            }else if( j==-1 ){
                //结束条件是 j==-1
                result.add( 0, list.get(i) );
            }
        }

        return result.get( k-1 );
    }

    public List<Integer> getList() {
        return list;
    }

    public void setList(List<Integer> list) {
        this.list = list;
    }

    /**
     * 方法名：main 说明：测试
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[] {9,1,2,4,5,6,7,8,10,3};
        System.out.println(quickSelect(a, 0, a.length - 1,3));
        FindK findK = new FindK();
        List<Integer> list = new ArrayList<>();
        list = Arrays.asList(new Integer[]{9,1,2,4,5,6,7,8,10,3});
        findK.setList(list);
        int b = findK.kSortThenCompare(4);
        System.out.println(b);


    }
}
